// -*- coding: utf-8 -*- 

package com.LeetCodeT.Greedy;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-03 15:53
 * IDE: IntelliJ IDEA
 * Introduction:
 */

@SuppressWarnings({"AlibabaClassNamingShouldBeCamel", "AlibabaUndefineMagicConstant"})
public class LargestSumAfterKNegations {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 取反给定数组并且获取该数组的最大值,可以多次选择同一个下标
        Arrays.sort(nums);
        int num = 0;
        if (nums[0] > 0) {
            // 给定数组并没有负数
            if (k % 2 != 0) {
                num = -nums[0];
            }
            return Arrays.stream(nums).sum() + 2 * num;
        } else if (nums[0] == 0) {
            // 给定数组最小值为0则将所有符号变更施加在0上
            return Arrays.stream(nums).sum();
        }

        // 给定数组存在负数
        for (int i = 0; i < k; i++) {
            // 当数组中不存在0，只存在正数和负数，则将最后的符号都用在最小的值上
            if (i >= nums.length) {
                int tmp = k - i;
                if (tmp % 2 != 0) {
                    num = -nums[nums.length - 1];
                }
                break;
            }
            if (i > 0 && nums[i] > 0) {
                // 剩下需要变更的符号次数，运用于相邻两个数字中最小的那位
                int remain = k - i;
                if (remain % 2 != 0) {
                    num = -Math.min(nums[i - 1], nums[i]);
                }
                break;
            }
            nums[i] = -nums[i];
        }
        return Arrays.stream(nums).sum() + 2 * num;
    }

    @Test
    public void shout00() {
        int[] nums = {-4, -2, -3};
        int k = 4;
        System.out.println(largestSumAfterKNegations(nums, k));
    }

}
